import com.sun.source.tree.Tree;

public class J101601 {

    public static class BinarySearchTree {

        static class TreeNode {
            public int key;
            public TreeNode left;
            public TreeNode right;

            TreeNode(int key) {
                this.key = key;
            }
        }

        public TreeNode root;

        /**
         * 插入一个元素
         * @param key
         */
        public boolean insert(int key) {
            if(root == null){
                root = new TreeNode(key);
                return true;
            }
            TreeNode cur = root;
            while(true){
                if(cur.key == key){
                    return false;
                }else if(key < cur.key){
                    if(cur.left == null){
                        cur.left = new TreeNode(key);
                        return true;
                    }
                    cur = cur.left;
                }else{
                    if(cur.right == null){
                        cur.right = new TreeNode(key);
                        return true;
                    }
                    cur = cur.right;
                }
            }
        }
        //查找key是否存在
        public TreeNode search(int key) {
            TreeNode cur = root;
            while(cur != null){
                if(cur.key == key){
                    return cur;
                }else if(key < cur.key){
                    cur = cur.left;
                }else{
                    cur = cur.right;
                }
            }
            return null;
        }
        //删除key的值
        public boolean remove(int key) {
            TreeNode parent = null;
            TreeNode cur = root;
            while (cur != null) {
                if (key == cur.key){
                    break;
                }
                parent = cur;
                if (key < cur.key){
                    cur = cur.left;
                } else {
                    cur = cur.right;
                }
            }
            if(cur != null){
               if (cur.left == null && cur.right == null) {
                   if (cur == root) {
                       root = null;
                   } else {
                       if (parent.left == cur) {
                           parent.left = null;
                       } else {
                           parent.right = null;
                       }
                   }
               } else if (cur.left != null && cur.right == null) {
                   if (cur == root) {
                       root = root.left;
                   } else {
                       if (parent.left == cur) {
                           parent.left = cur.left;
                       } else {
                           parent.right = cur.left;
                       }
                   }
               } else if (cur.left == null && cur.right != null) {
                   if (cur == root) {
                       root = root.right;
                   } else {
                       if (parent.left == cur) {
                           parent.left = cur.right;
                       } else {
                           parent.right = cur.right;
                       }
                   }
               } else {
                   TreeNode par = cur;
                   TreeNode rightMix = cur.right;
                   while (rightMix.left != null) {
                       par = rightMix;
                       rightMix = rightMix.left;
                   }
                   if (par == cur) {
                       rightMix.left = cur.left;
                       if (cur == root) {
                           root = rightMix;
                       } else if (parent.left == cur) {
                           parent.left = rightMix;
                       } else {
                           parent.right = rightMix;
                       }
                   } else {
                       cur.key = rightMix.key;
                       par.left = null;
                   }
               }
               return true;
            }
            return false;
        }
        public void myPrint(TreeNode root){
            if(root == null){
                return;
            }
            System.out.print(root.key + " ");
            myPrint(root.left);
            myPrint(root.right);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(13);
        tree.insert(8);
        tree.insert(19);
        tree.insert(4);
        tree.insert(11);
        tree.insert(15);
        tree.insert(20);
        tree.insert(3);
        tree.insert(5);
        tree.insert(8);
        tree.insert(12);
        tree.myPrint(tree.root);
        System.out.println();
        tree.remove(8);
        tree.myPrint(tree.root);
    }
}
